The present invention relates to a content addressable memory and, more particularly, to a hardware structure of a content addressable memory for reducing power consumption and occupation area.
In recent years, in network equipment such as a router and a switch, a content addressable memory (CAM) is widely used for search for a path of a network address or control of an access control list (ACL) of filtering. For example, in routing of a network address, the following process is executed. When a packet arrives at a router or a switch installed in the Internet environment, a network packet processing unit (NPU) in the router or switch analyzes the header of the arrived packet, and starts an address search to find the next hop destination (path). In the address search, the CAM is an LSI (Large Scale Integrated circuit) that provides the address search on the hardware base.
The destination network address written in the header of the packet is input as search request data for the next hop destination address search to the CAM. The CAM performs simultaneous parallel comparison between a list of data sequences of network addresses internally pre-stored and the input search request data. In the case where a matched address exists, the CAM outputs the index of the matched address. The NPU refers to the address of the next hop destination from the matched address index from the CAM. A concrete hop destination address is often written in another memory LSI such as an SRAM (Static Random Access Memory), not in the CAM itself.
On the other hand, in the case where there is no match with the data sequences stored in the CAM, the next hop destination address of the arrived packet is searched by a method different from the CAM hardware search. For example, when the addresses are not stored in the CAM but are written in another large-capacity memory, the large-capacity memory is accessed and a search on the software basis is performed. Alternatively, the packet is discarded as it is. Also in the case where no matched address exists in the CAM and long search time on the software basis is necessary, generally, the destination address (the next hop destination address) is written to the CAM and the storage data is updated as learning for the next packet having the same header. By the operation, a search of long process time by the software is performed only once. From the next time on, high-speed search on the CAM hardware basis can be performed. The advantage of the CAM in the application is increased.
The process performed in the case of the use for ACL control is similar to that in a search for a network address path. The ACL is an application which is frequently used nowadays in a router or a switch installed in a company or a school. By a combination of port numbers or the like indicative of the transmitter of a packet and the kind, discarding of the packet is controlled. The discarding control can be usually freely rewritten by the user (network administrator) by software. In the discarding control, by simultaneous parallel comparison between an input packet header and data written in the CAM by the user (network administrator), a search is executed at high speed on the hardware basis. According to the search result, an LSI different from the CAM is referred to. However, in the case of the ACL discharging control, different from the case of the address path search, a concrete process is often simply “permit: permission of passage of a packet” or “deny: discarding of a packet”.
As described above, an advantage of an address search on the CAM hardware basis is high effective search performance. The search performance is constant irrespective of the size of a data sequence held (bit width). In the case of a search on the software basis using a general memory, various studies using a tree and the like have been reported. However, in the case of a search on the software basis, generally, the larger the held data amount becomes, the longer the time of loading all of data to the outside becomes. That is, in the case of using a general memory, there is a characteristic that time required for an address search increases in proportional to the capacity of a database. This is a big issue when considering increase in the population of the Internet in recent years. Therefore, the address search on the CAM hardware basis is highly evaluated for such a use of the packet transfer control also from the viewpoint that the search performance does not depend on the size of a database.
An example of the configuration of such a CAM is disposed in patent document 1 (Japanese patent laid-open No. 2003-123482). In the patent document 1, SRAM cells are applied as CAM cells and TCAM (Ternary CAM) cells. In the configuration shown in the patent document 1, each memory cell is provided with a match detecting circuit (XOR circuit), and match/mismatch between stored data bits and search data bits is determined on a bit unit basis.
A configuration of comparing the size of search data and that of data stored in a CAM is disclosed in patent document 2 (Japanese patent laid-open No. 2005-129218). In the configuration described in the patent document 2, as memory cells, data memory cells for storing data values and mask memory cells for storing mask values are provided. A size comparator for comparing the size of data stored in the data memory cell and that of input data is also provided. The size comparator receives a size instruction signal (carry) from a memory cell in the ante stage, effectively performs a subtracting process, and outputs a signal indicative of the result of the comparison (subtraction result) to the next stage.
A CAM having the function of performing match comparison and size comparison is disclosed in patent document 3 (Japanese patent laid-open No. 2004-295967). In the configuration described in the patent document 3, a size comparator and a match comparator are provided for each of CAM cells.
A configuration of determining match/mismatch of a tag address of a cache memory is disclosed in patent document 4 (Japanese patent laid-open No. 2001-210081). In the configuration shown in the patent document 4, information corresponding to a tag address is read from a tag storage in accordance with the tag address. An exclusive OR operation between the read information and an address signal given from an address bus is executed in a column selection gate, and the computation result is output to the sense amplifier. By providing the exclusive OR computing function of a column selection gate, the exclusive OR computation is executed on a weak read signal on a bit line in the tag storage to generate a hit/miss signal. Therefore, at a timing earlier than the logic computation at a CMOS level, the exclusive OR computation result is generated to retrieve a tag at high speed.
Patent document 1: Japanese patent laid-open No. 2003-123482
Patent document 2: Japanese patent laid-open No. 2005-129218
Patent document 3: Japanese patent laid-open No. 2004-295967
Patent document 4: Japanese patent laid-open No. 2001-210081